package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 66. 加一
 * @date 2024/10/14 16:31
 */
public class E66 {
    /**
     * <h3>方法一：递归</h3>
     *
     * @param digits 存放数的数组
     * @return 加一后的数组
     */
    public int[] plusOne1(int[] digits) {
        int lastIndex = digits.length - 1;
        if (plusOne(digits, lastIndex)) {
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            return result;
        }
        return digits;
    }

    /**
     * 递归
     *
     * @param digits    数组
     * @param lastIndex 最后一个索引
     * @return 最低位进1返回true，否则返回false
     */
    private boolean plusOne(int[] digits, int lastIndex) {
        if (lastIndex < 0) {
            return true;
        }
        if (digits[lastIndex] == 9) {
            digits[lastIndex] = 0;
            return plusOne(digits, lastIndex - 1);
        }
        digits[lastIndex]++;
        return false;
    }

    /**
     * <h3>方法二：迭代</h3>
     *
     * @param digits 数的数组
     * @return 数加一后的结果
     */
    public int[] plusOne2(int[] digits) {
        int lastIndex = digits.length - 1;
        while (lastIndex >= 0) {
            if (digits[lastIndex] == 9) {
                digits[lastIndex] = 0;
                lastIndex--;
                continue;
            }
            digits[lastIndex]++;
            break;
        }
        if (lastIndex < 0) {
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            return result;
        }
        return digits;
    }

    /**
     * <h3>方法三：好理解的方式，循环用进位</h3>
     *
     * @param digits 数的数组
     * @return 数加一后的结果
     */
    public int[] plusOne3(int[] digits) {
        int carry = 1; // 进位
        // 1. 从后往前加一，更新进位
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i] += carry;
            // 如果为10，继续进位
            if (digits[i] == 10) {
                digits[i] = 0;
            }
            // 如果为0，则不需要进位，说明计算完成，提前结束
            else {
                return digits;
            }
        }
        // 到这里肯定是11111这种的，需要新建一个数组，把进位1加到最前面
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        System.arraycopy(digits, 0, result, 1, digits.length);
        return result;
    }
}
